package 常见算法查找;

public class 分块查找 {
    public static void main(String[] args) {
         /*
            分块查找
            核心思想：
                块内无序，块间有序
            实现步骤：
                1.创建数组blockArr存放每一个块对象的信息
                2.先查找blockArr确定要查找的数据属于哪一块
                3.再单独遍历这一块数据即可
        */
        //1.将数据分块
        //18开根号4.25块优化后3块
        int[] arr = {16, 5, 9, 12, 21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};


        //创建三个块的对象
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(73, 12, 17);


        //定义数组用来管理三个块的对象（索引表）
        Block[] brr = {b1, b2, b3};

        //定义一个变量用来记录要查找的元素
        int number = 37;

        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(brr, arr, number);
        System.out.println(index);


    }

    //利用分块查找的原理，查询number的索引
    public static int getIndex(Block[] brr, int[] arr, int number) {
        //1.确定number是在那一块当中
        int indexBlock = findIndexBlock(brr, number);
        System.out.println(indexBlock);
        if (indexBlock == -1) {
            System.out.println("不存在");
            return -1;
        }
        for (int i = brr[indexBlock].getStarIndex(); i <= brr[indexBlock].getEndIndex(); i++) {
            if (number==arr[i]){
                return i;
            }
        }
        return 0;
    }
    public static int findIndexBlock(Block[] brr, int number) {//1.确定number是在那一块当中
        for (int i = 0; i < brr.length; i++) {
            if (number < brr[i].getMax()) {
                return i;
            }
        }
        return -1;
    }

}

class Block {
    private int max;
    private int starIndex;
    private int endIndex;

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStarIndex() {
        return starIndex;
    }

    public void setStarIndex(int starIndex) {
        this.starIndex = starIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public Block(int max, int starIndex, int endIndex) {
        this.max = max;
        this.starIndex = starIndex;
        this.endIndex = endIndex;
    }

}
